package hw.q2;
import java.util.*;
/*
* 输入处理：

首先读取步骤数 N 和每个步骤的时间。
通过一个邻接表 dependencies 和一个 inDegree 数组来记录每个步骤的依赖关系和入度（即依赖它的步骤数量）。、
当作一个有向图来做
拓扑排序：

使用一个队列来存储入度为 0 的步骤（即没有依赖的步骤），作为拓扑排序的起点。
在处理每个步骤时，更新其依赖步骤的最早完成时间，并减少这些步骤的入度。如果某个步骤的入度减少到 0，就将其加入队列。
动态规划计算最短时间：

earliestCompletion 数组记录每个步骤的最早完成时间。
在拓扑排序的过程中，不断更新每个步骤的最早完成时间，最终得到整个安装过程的最短完成时间*/
public class SoftwareDeploymentScheduler {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取步骤总数 N
        int N = scanner.nextInt();
        int[] time = new int[N]; // 每个步骤的执行时间
        List<List<Integer>> dependencies = new ArrayList<>(); // 依赖关系的邻接表

        // 初始化时间数组和依赖列表
        for (int i = 0; i < N; i++) {
            time[i] = scanner.nextInt();
            dependencies.add(new ArrayList<>());
        }

        // 记录每个步骤的入度
        int[] inDegree = new int[N];

        // 读取依赖关系
        scanner.nextLine(); // 清除缓冲区中的换行符
        for (int i = 0; i < N; i++) {
            String line = scanner.nextLine().trim();
            if (!line.equals("-1")) {
                String[] parts = line.split(" ");
                for (String part : parts) {
                    int dep = Integer.parseInt(part) - 1;
                    dependencies.get(dep).add(i);
                    inDegree[i]++;
                }
            }
        }

        // 计算最短安装时间
        int result = calculateMinimumTime(N, time, dependencies, inDegree);
        System.out.println(result);
    }

    private static int calculateMinimumTime(int N, int[] time, List<List<Integer>> dependencies, int[] inDegree) {
        Queue<Integer> queue = new LinkedList<>();
        int[] earliestCompletion = new int[N];

        // 将所有入度为0的步骤加入队列
        for (int i = 0; i < N; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                earliestCompletion[i] = time[i];
            }
        }

        int maxTime = 0;

        // 进行拓扑排序并计算最早完成时间
        while (!queue.isEmpty()) {
            int current = queue.poll();
            int currentTime = earliestCompletion[current];

            // 更新 maxTime 为当前步骤的完成时间
            maxTime = Math.max(maxTime, currentTime);

            // 遍历当前步骤的依赖步骤
            for (int next : dependencies.get(current)) {
                earliestCompletion[next] = Math.max(earliestCompletion[next], currentTime + time[next]);
                inDegree[next]--;

                // 如果入度为0，加入队列
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return maxTime;
    }
}